// 给定一个二叉树，判断它是否是高度平衡的二叉树，即左右两个子树的高度差的绝对值不超过1
// 一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

// 思路：后序遍历，通过判断左右子树的高度差是否大于1来判断是否平衡，如果不平衡则返回-1
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小

function isBalanced(root) {
    function dfs(root) {
        if (!root) {
            return 0
        }
        let leftHeight = dfs(root.left)
        let rightHeight = dfs(root.right)
        if (leftHeight === -1 || rightHeight === -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1
        }
        return Math.max(leftHeight, rightHeight) + 1
    }
    return dfs(root) !== -1
}


const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
            // left: {
            //     val: 3.1
            // }
        },
    },
    right: {
        val: 6,
    },
};

console.log(isBalanced(root))